package q567_checkInclusion;

public class Solution_2 {
    /*
    双指针解法
    结合solution1的思路 我们使用了两个数组来判断是否相等来解决该问题
    那么是否能够使用一个数组cnt 对于s1中每一个字符 cnt中对应位置记录该字符的个数的 负数
    然后从s2的开头开始遍历 分别用两个指针考察对应的区间
    指针移动时要保证cnt中每个数都不为正数
    而当cnt达到了s1的长度 也就找到了对应的排列
     */
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt = new int[26];
        /*
        首先使用一个cnt存储s1中每一个字符出现次数的 负数
        假设s1是一个abc这样的字符串
        那么cnt应该是
        -1 -1 -1 0 0 0 。。。。0
         */
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
        }
        // 使用双指针来判断
        int left = 0;
        for (int right = 0; right < m; ++right) {
            // 读取right指针的字符
            int x = s2.charAt(right) - 'a';
            // 然后cnt中对应字符位置+1
            ++cnt[x];
            /*
            考虑是否出现了正数
            有两种情况
            1 此时读取的字符是s1中的字符
            2 此时读取的不是s1中的字符
            之所以要使用while循环 我们可以考虑这样的情况 一开始s1是abc
            我们读入了a b d
            而right到达d时 cnt对应d的位置变成了1 显然abd不是一个组合
            所以我们要一直移动left 把 d以及d前面的那些字符对应位置的值全部清除

            而如果是abb则要一直清除到b的位置 b将会被保留
             */
            while (cnt[x] > 0) {
                --cnt[s2.charAt(left) - 'a'];
                ++left;
            }
            // 经过上面的操作 如果发现有一段的长度正好是n 也就意味着我们找到了一个排列
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;

    }
}
